package linkList;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class Solution_2 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    /**
     * 206. 反转链表 -easy
     * @param head
     * @return
     * 1.双指针法；2.递归法
     */
    //1. 双指针法
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = new ListNode();
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            //两指针后移
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    //根据双指针移动的过程，进行递归实现
    public ListNode reverseList2(ListNode head) {
        return reverse(null, head);

    }
    public ListNode reverse(ListNode pre, ListNode cur) {
        //递归结束条件
        if (cur == null) {
            return pre;
        }
        //递归逻辑
        ListNode temp = cur.next;
        cur.next = pre;
        //递归调用
        return reverse(cur, temp);
    }

    /**
     * 使用虚拟头节点 进行反转
     * 注意最后的返回值
     */
    public ListNode reverseList1(ListNode head) {
        //创建虚拟头结点
        ListNode dummy = new ListNode(-1,null);
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            //头插法
            cur.next = dummy.next;
            dummy.next = cur;
            cur = temp;

        }
        return dummy.next;
    }

    /**
     * 24. 两两交换链表中的节点 -medium
     * @param head
     * @return
     */

    public ListNode swapPairs(ListNode head) {
        //设计虚拟头节点，指向头节点，这才方便操作第一个和第二个节点
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        //需要这两个临时变量
        ListNode firstNode =null;
        ListNode secondNode =null;
        while(cur.next != null && cur.next.next != null) {
            secondNode = cur.next.next;
            firstNode = cur.next;
            cur.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;
            //cur指向下一次要交换的两节点的前一个节点
            //思考发现是firstNode
            cur = firstNode;
        }
        return dummy.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点 -medium
     * @param head
     * @param n
     * @return
     * 思路是：找到要删除的节点的前一个节点，使前一个节点的next 指向其next的next
     * 双指针的经典应用，如果要删除倒数第n个节点，
     * 让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。
     * 此时slow指向要删除节点的前一个节点，删掉slow所指向的节点就可以了。
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dumpyNode=new ListNode(0,head);
        ListNode fast=dumpyNode;
        ListNode slow=dumpyNode;
        for(int i=0;i<n;i++)
        {
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dumpyNode.next;

    }

    /**
     * 160. 相交链表 -easy
     * @param headA
     * @param headB
     * @return
     */
    //1.双指针法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        //这里不能用curA.val != curB.val 因为curA和curB可能为null
        //判断节点相交，即节点对象是否是同一个对象，所以这里!=是对的。比的是两个对象的引用
        while(curA != curB) {
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }
        return curA;

    }
    //2.用哈希表做--注意判断相交即有同一个节点对象，所以是节点对象的引用是否一致
    //而不是节点对象的值是否一致
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        ListNode cur = headA;
        while(cur != null) {
            set.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while(cur != null) {
            if(set.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 142. 环形链表 II -medium
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        //1.用快慢指针，如果有环，快慢指针一定会在环里某处相遇，类比于两个速度不同的
        //人在操场跑步，快的人跑的快，慢的人跑的慢，快慢指针一定会相遇，
        //而且此时慢指针一定没跑完一圈，而且快指针一定至少跑过一圈
        // 而且因为是快慢指针，它们一定不可能在环的入口处相遇
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                //相遇了
                ListNode index1 = head;
                ListNode index2 = slow;
                while(index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                //根据公式推到，相当于从头开始一个指针，从相遇点一个指针，
                // 步速相同，相遇点就是环的入口点
                return index1; // 返回环的入口点
            }
        }
        return null;
    }


    public ListNode detectCycle_1(ListNode head) {
        //2.用哈希表做
        Set<ListNode> set = new HashSet<>();
        int index = 0;
        //遍历链表，存入哈希表中，如果有环，一定会有重复的节点，即哈希表中一定存了该节点
        ListNode cur = head;
        while(cur != null) {
            if(set.contains(cur)) {
                return cur;
            } else {
                set.add(cur);
            }
            cur = cur.next;
        }
        return null;
    }


}
